{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Decode XORed Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: decode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #解码异或后的排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>perm</code> ，它是前 <code>n</code> 个正整数的排列，且 <code>n</code> 是个 <strong>奇数</strong> 。</p>\n",
    "\n",
    "<p>它被加密成另一个长度为 <code>n - 1</code> 的整数数组 <code>encoded</code> ，满足 <code>encoded[i] = perm[i] XOR perm[i + 1]</code> 。比方说，如果 <code>perm = [1,3,2]</code> ，那么 <code>encoded = [2,1]</code> 。</p>\n",
    "\n",
    "<p>给你 <code>encoded</code> 数组，请你返回原始数组 <code>perm</code> 。题目保证答案存在且唯一。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>encoded = [3,1]\n",
    "<b>输出：</b>[1,2,3]\n",
    "<b>解释：</b>如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>encoded = [6,5,4,6]\n",
    "<b>输出：</b>[2,4,1,5,3]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= n &lt; 10<sup>5</sup></code></li>\n",
    "\t<li><code>n</code> 是奇数。</li>\n",
    "\t<li><code>encoded.length == n - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [decode-xored-permutation](https://leetcode.cn/problems/decode-xored-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [decode-xored-permutation](https://leetcode.cn/problems/decode-xored-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1]', '[6,5,4,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        #Optional 可选参数\n",
    "        def decodeNode(ln: ListNode) -> str:\n",
    "            snum = \"\"\n",
    "            i = ln\n",
    "            while(i != None):\n",
    "                snum += str(i.val)\n",
    "                i = i.next\n",
    "            return snum\n",
    "\n",
    "        def encodeNode(n: int) -> ListNode:\n",
    "            sn = str(n)[::-1]\n",
    "            # print(sn)\n",
    "            lnnext = ListNode(val=int(sn[0]))\n",
    "            for i in range(1,len(sn)):\n",
    "                lnnum = ListNode(int(sn[i]),lnnext)\n",
    "                lnnext = lnnum\n",
    "            return lnnext\n",
    "\n",
    "            \n",
    "        s1 = decodeNode(l1)\n",
    "        s2 = decodeNode(l2)\n",
    "        \n",
    "        ia = int(s1) + int(s2)\n",
    "        # print(s1,s2,ia)\n",
    "        return encodeNode(ia)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        n = len(order)\n",
    "        order_dict = {}\n",
    "        for i, ch in enumerate(order):\n",
    "            order_dict[ch] = i \n",
    "        for i, ch in enumerate(s):\n",
    "            if ch not in order_dict:\n",
    "                order_dict[ch] = 999 + i\n",
    "\n",
    "\n",
    "        encode_s = []\n",
    "        for ch in s:\n",
    "            encode_s.append(order_dict[ch])\n",
    "        \n",
    "        id2ch = {}\n",
    "        for k, v in order_dict.items():\n",
    "            id2ch[v] =k\n",
    "\n",
    "        encode_s.sort()\n",
    "\n",
    "        decode_s = []\n",
    "        for i in encode_s:\n",
    "            decode_s.append(id2ch[i])\n",
    "\n",
    "        return ''.join(decode_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        num_stack = list()\n",
    "        stack = list()\n",
    "        for ch in s:\n",
    "            if ch >=\"0\" and ch <=\"9\":\n",
    "                num_stack.append(ch)\n",
    "            elif ch == '[':\n",
    "                stack.append(ch) \n",
    "                # pop num\n",
    "                nums = list()\n",
    "                while num_stack:\n",
    "                    if type(num_stack[-1]) is int:\n",
    "                        break\n",
    "                    else:\n",
    "                        nums.insert(0,num_stack.pop())\n",
    "                num_stack.append(int(\"\".join(nums)))\n",
    "            \n",
    "            elif ch >='a' and ch<='z':\n",
    "                stack.append(ch)\n",
    "            else:\n",
    "                #  ch == ']'\n",
    "                chars = list()\n",
    "                while stack:\n",
    "                    top = stack.pop()\n",
    "                    if top !='[':\n",
    "                        chars.insert(0, top)\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "                stack.append(\"\".join(num_stack.pop()*chars))\n",
    "        return \"\".join(stack)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        cur = 0\n",
    "        n = len(s)\n",
    "        ss = ''\n",
    "        while cur < n:\n",
    "            c = s[cur]\n",
    "            if ord(c) >= 48 and ord(c) <= 57:\n",
    "                start = cur\n",
    "                while ord(s[cur]) >= 48 and ord(s[cur]) <= 57:\n",
    "                    cur += 1\n",
    "                stack1.append(int(s[start:cur]))\n",
    "                stack2.append(ss)\n",
    "                ss = ''\n",
    "            elif c == ']':\n",
    "                ss = stack2.pop() + stack1.pop() * ss\n",
    "            else:\n",
    "                ss += s[cur]\n",
    "            cur += 1\n",
    "        return ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def gen_string1(rep,sub_str):\n",
    "            temp =''\n",
    "            for i in range(0,rep):\n",
    "                temp+=(sub_str)\n",
    "            return temp\n",
    "\n",
    "        def gen_string_main(new_str):\n",
    "            rep = 0\n",
    "            ptn_start =len(new_str)-1\n",
    "            while new_str[ptn_start]!='[':\n",
    "                 ptn_start -=1\n",
    "            rep_start = ptn_start -1\n",
    "            while ord('0')<= ord(new_str[rep_start] )<=ord('9') :\n",
    "                rep_start-=1\n",
    "            rep = int(new_str[rep_start+1:ptn_start])\n",
    "            ptn_end = ptn_start+1\n",
    "            while new_str[ptn_end]!=']':\n",
    "                  ptn_end+=1\n",
    "            temp1 = new_str[0:rep_start+1]\n",
    "            temp2 = gen_string1(rep,new_str[ptn_start+1:ptn_end])\n",
    "            temp3 = new_str[ptn_end+1:len(new_str)]\n",
    "            return temp1 + temp2 + temp3\n",
    "\n",
    "        while '[' in s or ']' in s:\n",
    "          s =   gen_string_main(s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        temp_res = []\n",
    "        cur_str = ''\n",
    "        cur_num = 0\n",
    "        for char in s:\n",
    "            if char == '[':\n",
    "                temp_res.append(cur_str)\n",
    "                temp_res.append(cur_num)\n",
    "                cur_str = ''\n",
    "                cur_num = 0\n",
    "            elif char == ']':\n",
    "                pre_num = temp_res.pop()\n",
    "                pre_str = temp_res.pop()\n",
    "                cur_str = pre_str + pre_num * cur_str\n",
    "            elif char.isdigit():\n",
    "                cur_num = cur_num * 10 + int(char)\n",
    "            else:\n",
    "                cur_str += char\n",
    "                \n",
    "        return cur_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if s[i]!=\"]\":\n",
    "                stack.append(s[i])\n",
    "            else:\n",
    "                temp = \"\"\n",
    "                t = stack.pop()\n",
    "                while(t!='['):\n",
    "                    temp = t + temp\n",
    "                    t = stack.pop()\n",
    "                count =\"\"\n",
    "                while(stack and stack[-1].isdigit()):\n",
    "                    count = stack.pop() + count\n",
    "                count = int(count)\n",
    "                temp = temp*count\n",
    "                stack.append(temp)\n",
    "        res = \"\".join(stack)\n",
    "        return res\n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack = []\n",
    "        aws = ''\n",
    "        for char in s:\n",
    "            if char != ']':\n",
    "                stack.append(char)\n",
    "                print(stack)\n",
    "            if char == ']':\n",
    "                res = ''\n",
    "                for i in range(len(stack)):\n",
    "                    temp = stack.pop()\n",
    "                    print('temp:', temp)\n",
    "                    if temp != '[':\n",
    "                        res += temp\n",
    "                    if temp == '[':\n",
    "                        times = ''\n",
    "                        print('len(stack)', len(stack), stack)\n",
    "                        for _ in range(len(stack)):\n",
    "                            time = stack.pop()\n",
    "                            if time.isdigit():\n",
    "                                times += time\n",
    "                            else:\n",
    "                                stack.append(time)\n",
    "                                break\n",
    "                            \n",
    "                        times = times[::-1]\n",
    "                        res *= int(times)\n",
    "                        # res = res[::-1]\n",
    "                        stack.append(res)\n",
    "                        break\n",
    "                print(\"stack\",stack)\n",
    "                \n",
    "\n",
    "        return ''.join([s[::-1] for s in stack])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        multi = 0\n",
    "        res = ''\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = '', 0\n",
    "            elif ch == ']':\n",
    "                cur_mult, cur_res = stack.pop()\n",
    "                res = cur_res + cur_mult * res\n",
    "            elif '0' <= ch <= '9':\n",
    "                multi = multi * 10 + int(ch)\n",
    "            else:\n",
    "                res += ch\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)            \n",
    "            else:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                multi, res = 0, \"\"\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi*res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi*10 + int(c)\n",
    "            else:\n",
    "                res += c\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)            \n",
    "            else:\n",
    "                res += c\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        num = 0\n",
    "        res = \"\"\n",
    "        numStack = []\n",
    "        strStack = []\n",
    "        for i in s:\n",
    "            if i.isdigit():\n",
    "                num = num * 10 + int(i)\n",
    "            elif i == \"[\":\n",
    "                numStack.append(num)\n",
    "                strStack.append(res)\n",
    "                num, res = 0, \"\"\n",
    "            elif i == \"]\":\n",
    "                num = numStack.pop()\n",
    "                string = strStack.pop()\n",
    "                res = string + res * num \n",
    "                num = 0\n",
    "            else:\n",
    "                res += i\n",
    "        return res\n",
    "\n",
    "        # stack = []  # (str, int) 记录之前的字符串和括号外的上一个数字\n",
    "        # num = 0\n",
    "        # res = \"\"  # 实时记录当前可以提取出来的字符串\n",
    "        # for c in s:\n",
    "        #     if c.isdigit():\n",
    "        #         num = num * 10 + int(c)\n",
    "        #     elif c == \"[\":\n",
    "        #         stack.append((res, num))\n",
    "        #         res, num = \"\", 0\n",
    "        #     elif c == \"]\":\n",
    "        #         top = stack.pop()\n",
    "        #         res = top[0] + res * top[1]\n",
    "        #     else:\n",
    "        #         res += c\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        def f(m):\n",
    "            return int(m.group(1)) * m.group(2)\n",
    "        while '[' in s:\n",
    "            s = re.sub(r'(\\d+)\\[([A-Za-z]*)\\]',f,s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack=[]\n",
    "        n=len(s)\n",
    "        ans=''\n",
    "        sz={'1':1,\"2\":2,\"3\":3,\"4\":4,\"5\":5,\"6\":6,'7':7,'8':8,'9':9,'0':0}\n",
    "        i=0\n",
    "        while i <n:\n",
    "            if s[i] in sz:\n",
    "                co=0\n",
    "                while s[i]in sz:\n",
    "                    co=co*10+sz[s[i]]\n",
    "                    i+=1\n",
    "                stack.append(co)\n",
    "            elif s[i] == ']':\n",
    "                cur=''\n",
    "                while stack[-1]!='[':\n",
    "                    cur=stack[-1]+cur\n",
    "                    stack.pop()\n",
    "                stack.pop()\n",
    "                k=stack.pop()\n",
    "                cur=cur*k\n",
    "                stack.append(cur)\n",
    "                i+=1\n",
    "            else:\n",
    "                stack.append(s[i])\n",
    "                i+=1\n",
    "        for i in stack:\n",
    "            ans+=i\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        while '[' in s:\n",
    "            s = self.replaceOne(s)\n",
    "        return s\n",
    "\n",
    "    def replaceOne(self, s) -> str:\n",
    "        def getnew(matched):\n",
    "            return int(matched.group('num')) * matched.group('chr')\n",
    "\n",
    "        pat = re.compile(r'(?P<num>\\d+)\\[(?P<chr>[a-z]+)\\]', re.I)\n",
    "        return re.sub(pat, getnew, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    " \n",
    "        stack,res, multi = [], \"\", 0\n",
    "\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res,multi = '',0\n",
    "            elif c == ']':\n",
    "                cur_multi, cur_res = stack.pop()\n",
    "                res = cur_res + cur_multi * res \n",
    "            elif '0' <= c <='9':\n",
    "                multi = multi * 10 + int(c)\n",
    "            else:\n",
    "                res += c\n",
    "                \n",
    "        return res \n",
    "\n",
    "        # stack, res, multi = [], \"\", 0\n",
    "        # for c in s:\n",
    "        #     if c == '[':\n",
    "        #         stack.append([multi, res])\n",
    "        #         res, multi = \"\", 0\n",
    "        #     elif c == ']':\n",
    "        #         cur_multi, last_res = stack.pop()\n",
    "        #         res = last_res + cur_multi * res\n",
    "        #     elif '0' <= c <= '9':\n",
    "        #         multi = multi * 10 + int(c)            \n",
    "        #     else:\n",
    "        #         res += c\n",
    "        # return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res , multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)\n",
    "            else:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #  递归未掌握\n",
    "    def decodeString0(self, s: str) -> str:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i].isdigit():\n",
    "                for j in range(i + 1, n):\n",
    "                    if not s[j].isdigit():\n",
    "                        break\n",
    "                stack.append(int(s[i: j]))\n",
    "                i = j\n",
    "                continue\n",
    "            elif s[i] == '[':\n",
    "                stack.append(s[i])\n",
    "            elif s[i] == ']':\n",
    "                sub_s = ''\n",
    "                while True:\n",
    "                    ch = stack.pop()\n",
    "                    if ch == '[':\n",
    "                        break\n",
    "                    else:\n",
    "                        sub_s = ch + sub_s\n",
    "                sub_s *= stack.pop()\n",
    "                stack.append(sub_s)\n",
    "            else:\n",
    "                stack.append(s[i])\n",
    "            i += 1\n",
    "        return ''.join(stack)\n",
    "\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)            \n",
    "            else:\n",
    "                res += c\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def decodeString(self, s: str) -> str:\r\n",
    "        if len(s)<=2:\r\n",
    "            return s\r\n",
    "        \r\n",
    "        self.string = s\r\n",
    "        \r\n",
    "        res = self.decode(0, len(self.string)-1, 1)\r\n",
    "        return res\r\n",
    "            \r\n",
    "    def decode(self, left, right, rpt_time):\r\n",
    "        # print(left, right, rpt_time)\r\n",
    "        if left>right or right>=len(self.string):\r\n",
    "            return \"\"\r\n",
    "        \r\n",
    "        pam_stack = []\r\n",
    "        idx = left\r\n",
    "        \r\n",
    "        dec_str = \"\"\r\n",
    "        cur_tpr_str = \"\"\r\n",
    "        first_left = -100\r\n",
    "        \r\n",
    "        while idx<=right:\r\n",
    "            chr = self.string[idx]\r\n",
    "            if len(pam_stack) == 0:\r\n",
    "                if \"a\"<= chr <=\"z\":\r\n",
    "                    dec_str+=chr\r\n",
    "                elif chr==\"[\":\r\n",
    "                    pam_stack.append(chr)\r\n",
    "                    first_left = idx\r\n",
    "                elif chr.isdigit():\r\n",
    "                    cur_tpr_str+=chr\r\n",
    "            else:\r\n",
    "                if chr ==\"]\":\r\n",
    "                    pam_stack.pop()\r\n",
    "                    if len(pam_stack)==0:\r\n",
    "                        tmp_res = (dec_str+self.decode(first_left+1, idx-1, int(cur_tpr_str))+self.decode(idx+1, right, 1)) * rpt_time\r\n",
    "                        # print(left, right, rpt_time, tmp_res)\r\n",
    "                        return tmp_res\r\n",
    "                    \r\n",
    "                elif chr == \"[\":\r\n",
    "                    pam_stack.append(chr)\r\n",
    "            idx += 1\r\n",
    "        return dec_str*rpt_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def decodeString(self, s: str) -> str:\r\n",
    "        if len(s)<=2:\r\n",
    "            return s\r\n",
    "        \r\n",
    "        self.string = s\r\n",
    "        \r\n",
    "        res = self.decode(0, len(self.string)-1, 1)\r\n",
    "        return res\r\n",
    "            \r\n",
    "    def decode(self, left, right, rpt_time):\r\n",
    "        print(left, right, rpt_time)\r\n",
    "        if left>right or right>=len(self.string):\r\n",
    "            return \"\"\r\n",
    "        \r\n",
    "        pam_stack = []\r\n",
    "        idx = left\r\n",
    "        \r\n",
    "        dec_str = \"\"\r\n",
    "        cur_tpr_str = \"\"\r\n",
    "        first_left = -100\r\n",
    "        \r\n",
    "        while idx<=right:\r\n",
    "            chr = self.string[idx]\r\n",
    "            if len(pam_stack) == 0:\r\n",
    "                if \"a\"<= chr <=\"z\":\r\n",
    "                    dec_str+=chr\r\n",
    "                elif chr==\"[\":\r\n",
    "                    pam_stack.append(chr)\r\n",
    "                    first_left = idx\r\n",
    "                elif chr.isdigit():\r\n",
    "                    cur_tpr_str+=chr\r\n",
    "            else:\r\n",
    "                if chr ==\"]\":\r\n",
    "                    pam_stack.pop()\r\n",
    "                    if len(pam_stack)==0:\r\n",
    "                        tmp_res = (dec_str+self.decode(first_left+1, idx-1, int(cur_tpr_str))+self.decode(idx+1, right, 1)) * rpt_time\r\n",
    "                        print(left, right, rpt_time, tmp_res)\r\n",
    "                        return tmp_res\r\n",
    "                    \r\n",
    "                elif chr == \"[\":\r\n",
    "                    pam_stack.append(chr)\r\n",
    "            idx += 1\r\n",
    "        return dec_str*rpt_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "        self.prev = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.head = Node(None)\n",
    "        self.tail = Node(None)\n",
    "        self.stack = []\n",
    "        self.stackTop = -1\n",
    "\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        self.toList(s)\n",
    "\n",
    "        while self.stackTop >= 0:\n",
    "            startNode = self.stack[self.stackTop][0]\n",
    "            endNode = self.stack[self.stackTop][1]\n",
    "            self.stackTop -= 1\n",
    "        \n",
    "            p = startNode.next\n",
    "            one = \"\"\n",
    "            while p != endNode:\n",
    "                one += p.value\n",
    "                p = p.next\n",
    "            repeatNode = startNode.prev\n",
    "            tmp = \"\"\n",
    "            for i in range(0, repeatNode.value):\n",
    "                tmp += one\n",
    "\n",
    "            repeatNode.next = endNode.next\n",
    "            endNode.next.prev = repeatNode\n",
    "            repeatNode.value = tmp\n",
    "            \n",
    "        result = \"\"\n",
    "        p = self.head.next\n",
    "        while p != self.tail:\n",
    "            result += p.value\n",
    "            p = p.next\n",
    "        return result\n",
    "\n",
    "    def toList(self, s):\n",
    "        current = self.head\n",
    "        for i in range(0, len(s)):\n",
    "            if type(current.value) == int and self.isInt(s[i]):\n",
    "                current.value = 10 * current.value + int(s[i])\n",
    "                continue\n",
    "                \n",
    "            pre = current\n",
    "            current = Node(s[i])\n",
    "            if (self.isInt(current.value)):\n",
    "                current.value = int(current.value)\n",
    "            if (self.head.next == None):\n",
    "                self.head.next = current\n",
    "            if s[i] == '[':\n",
    "                self.stackTop += 1\n",
    "                self.stack.append([current, None])\n",
    "            if s[i] == ']':\n",
    "                t = self.stackTop\n",
    "                while self.stack[t][1] != None:\n",
    "                    t -= 1\n",
    "                self.stack[t][1] = current\n",
    "                    \n",
    "            pre.next = current\n",
    "            current.prev = pre\n",
    "        current.next = self.tail\n",
    "        self.tail.prev = current\n",
    "\n",
    "    def isInt(self, ss):\n",
    "        return ord('0') <= ord(ss) and ord(ss) <= ord('9')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        # stack=[]\n",
    "        # res=''\n",
    "        # mutil=0\n",
    "        # for c in s:\n",
    "        #     if c=='[':\n",
    "        #         stack.append([mutil,res])\n",
    "        #         res=''\n",
    "        #         mutil=0\n",
    "        #     elif c==']':\n",
    "        #         cur_multi,last_res=stack.pop()\n",
    "        #         res=last_res+cur_multi*res\n",
    "        #     elif '0'<=c <='9':\n",
    "        #         mutil=mutil*10+int(c)\n",
    "        #     else:\n",
    "        #         res+=c\n",
    "        # return res\n",
    "        stack,res,multi=[],'',0\n",
    "        for c in s :\n",
    "            if c=='[':\n",
    "                stack.append([multi,res])\n",
    "                res,multi='',0\n",
    "            elif c==']':\n",
    "                hidmulti,last_res=stack.pop()\n",
    "                res=last_res+hidmulti*res\n",
    "            elif '0'<=c<='9':\n",
    "                multi=multi*10+int(c)\n",
    "            else:\n",
    "                res+=c\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    start_point=0\n",
    "\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        if(self.start_point==len(s)):\n",
    "            return ''\n",
    "        while(True):\n",
    "            c=s[self.start_point]\n",
    "            if (c.isdigit()):\n",
    "                digit=self.getDigit(s[self.start_point:])\n",
    "                string1 = digit*self.decodeString(s)\n",
    "                return string1+self.decodeString(s)\n",
    "            else:\n",
    "                self.start_point += 1\n",
    "                if(c == '['):\n",
    "                    return self.decodeString(s)\n",
    "                elif(c == ']'):\n",
    "                    return ''\n",
    "                else:\n",
    "                    # c is a letter\n",
    "                    return c+self.decodeString(s)\n",
    "    \n",
    "    def getDigit(self, s: str) -> int:\n",
    "        result=''\n",
    "        for c in s:\n",
    "            if (c.isdigit()):\n",
    "                self.start_point+=1\n",
    "                result += c\n",
    "            else:\n",
    "                break\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)            \n",
    "            else:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        pwd_map = {ord(' '): ord(' ')}\n",
    "        start = 97\n",
    "\n",
    "        for char in key:\n",
    "            if ord(char) not in pwd_map:\n",
    "                pwd_map[ord(char)] = start\n",
    "                start += 1\n",
    "        return message.translate(pwd_map)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        pwd_map = {}\n",
    "        start = 97\n",
    "\n",
    "        for char in key:\n",
    "            if ord(char) not in pwd_map and char!=' ':\n",
    "                pwd_map[ord(char)] = start\n",
    "                start += 1\n",
    "        return message.translate(pwd_map)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        rules = dict()\n",
    "        cur = \"a\"\n",
    "\n",
    "        for c in key:\n",
    "            if c != \" \" and c not in rules:\n",
    "                rules[c] = cur\n",
    "                cur = chr(ord(cur) + 1)\n",
    "\n",
    "        result = \"\".join(rules.get(c, \" \") for c in message)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        idx = ord(\"a\")\n",
    "        mapping = dict()\n",
    "        mapping[\" \"] = \" \"\n",
    "        for k in key:\n",
    "            if k not in mapping:\n",
    "                mapping[k] = chr(idx)\n",
    "                idx += 1\n",
    "        assert len(mapping) == 27\n",
    "        return \"\".join([mapping[s] for s in message])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        i = 97\n",
    "        ma = {' ': ' '}\n",
    "        key = key.replace(' ','')\n",
    "        for k in key:\n",
    "\n",
    "            if k not in ma.keys():\n",
    "                ma[k] = chr(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                continue\n",
    "        # print(ma)\n",
    "        ans = ''\n",
    "        for s in message:\n",
    "\n",
    "            v = ma[s]\n",
    "            ans += v\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        letters = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        d = {}\n",
    "        a = 0\n",
    "        for k in key:\n",
    "            if k != ' ' and k not in d.keys():\n",
    "                d[k] = letters[a]\n",
    "                a += 1\n",
    "        n = ''\n",
    "        for m in message:\n",
    "            if m != ' ':\n",
    "                n += d[m]\n",
    "            else:\n",
    "                n += ' '\n",
    "        return n\n",
    "             \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        d = {\" \": \" \"}\n",
    "        i=0\n",
    "        for c in key:\n",
    "            if c not in d:\n",
    "                d[c] = ascii_lowercase[i]\n",
    "                i+=1\n",
    "        return \"\".join(d[c] for c in message)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        hash_d = {' ':' '}\n",
    "        cnt = 0\n",
    "        res = ''\n",
    "        for i in key:\n",
    "            if i not in hash_d:\n",
    "                hash_d[i] = chr(ord('a') + cnt)\n",
    "                cnt += 1\n",
    "        for i in message:\n",
    "            res += hash_d[i]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        cur = \"a\"\n",
    "        rules = dict()\n",
    "\n",
    "        for c in key:\n",
    "            if c != \" \" and c not in rules:\n",
    "                rules[c] = cur\n",
    "                cur = chr(ord(cur) + 1)\n",
    "\n",
    "        ans = \"\".join(rules.get(c, \" \") for c in message)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        mapVal = {}\n",
    "        iter = 0\n",
    "        for c in key:\n",
    "            if c not in mapVal and c!=\" \":\n",
    "                mapVal[c] = iter\n",
    "                iter += 1\n",
    "        print(mapVal)\n",
    "        ans = \"\"\n",
    "        for c in message:\n",
    "            if c == \" \":\n",
    "                ans += \" \"\n",
    "            else:\n",
    "                ans+=chr(mapVal[c]+97)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        hash_d = {' ':' '}\n",
    "        cnt = 0\n",
    "        res = ''\n",
    "        for i in key:\n",
    "            if i not in hash_d:\n",
    "                hash_d[i] = chr(ord('a') + cnt)\n",
    "                cnt += 1\n",
    "        for i in message:\n",
    "            res += hash_d[i]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        pwd_map = {}\n",
    "        start = 97\n",
    "\n",
    "        for char in key:\n",
    "            if ord(char) not in pwd_map and char!=' ':\n",
    "                pwd_map[ord(char)] = start\n",
    "                start += 1\n",
    "        return message.translate(pwd_map)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        table = {}\n",
    "        table[' '] = ' '\n",
    "        i = 0\n",
    "        for x in key:\n",
    "            if x in table:\n",
    "                continue\n",
    "            table[x] = chr(ord('a') + i)\n",
    "            i += 1\n",
    "        return ''.join([table[_] for _ in message])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dic = {\" \": \" \"}\n",
    "        ans = \"\"\n",
    "        i = 0\n",
    "        for c in key:\n",
    "            if c not in dic:\n",
    "                dic[c] = chr(ord(\"a\") + i)\n",
    "                i += 1\n",
    "        for c in message:\n",
    "            ans += dic[c]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        tmp={}\n",
    "        length=0\n",
    "        for i in key:\n",
    "            if i not in tmp and i!=\" \":\n",
    "                tmp[i]=length+97\n",
    "                length+=1\n",
    "\n",
    "        res=\"\"\n",
    "        for i in message:\n",
    "            if i!=\" \":\n",
    "                res+=(chr(tmp[i]))\n",
    "            else:\n",
    "                res+=i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dic = {}\n",
    "        length1 = len(key)\n",
    "        length2 = len(message)\n",
    "        count = 0\n",
    "        for i in range(length1):\n",
    "            if key[i] != ' ' and key[i] not in dic:\n",
    "                dic[key[i]] = chr(97 + count)\n",
    "                count = count + 1\n",
    "        \n",
    "        dic[' '] = ' '\n",
    "        num = \"\"\n",
    "        for i in range(length2):\n",
    "            num += dic[message[i]]\n",
    "        \n",
    "        return num\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        d = {\" \": \" \"}\n",
    "        i = 0\n",
    "        for c in key:\n",
    "            if c not in d:\n",
    "                d[c] = ascii_lowercase[i]\n",
    "                i += 1\n",
    "        return \"\".join(d[c] for c in message)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        output_list = []\n",
    "        \n",
    "        newkey=''\n",
    "        for char in key:\n",
    "            if char not in newkey:\n",
    "                newkey+=char\n",
    "        \n",
    "        qq=\"\".join(newkey.split(\" \"))\n",
    "        newqq=list(qq)\n",
    "        value=[\"a\",\"b\",\"c\",\"d\",\"e\",\"f\",\"g\",\"h\",\"i\",\"j\",\"k\",\"l\",\"m\",\"n\",\"o\",\"p\",\"q\",\"r\",\"s\",\"t\",\"u\",\"v\",\"w\",\"x\",\"y\",\"z\"]\n",
    "        dict1=dict(zip(newqq,value))\n",
    "        \n",
    "        \n",
    "        res=\"\"\n",
    "        for i in message:\n",
    "            res+=\" \" if i==\" \" else dict1[i]\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        cur = \"a\"\n",
    "        rules = dict()\n",
    "\n",
    "        for c in key:\n",
    "            if c != \" \" and c not in rules:\n",
    "                rules[c] = cur\n",
    "                cur = chr(ord(cur) + 1)\n",
    "\n",
    "        ans = \"\".join(rules.get(c, \" \") for c in message)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dc = dict()\n",
    "        all_alpha_1 = [chr(i) for i in range(ord('a'), ord('z') + 1)]\n",
    "        for k in key:\n",
    "            if k.isalpha():\n",
    "                dc.setdefault(k, None)\n",
    "        for k in dc:\n",
    "            dc[k] = all_alpha_1.pop(0)\n",
    "        out = ''.join([dc.get(i, ' ') for i in message])\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        hash_d = {' ':' '}\n",
    "        cnt = 0\n",
    "        res = ''\n",
    "        for i in key:\n",
    "            if i not in hash_d:\n",
    "                hash_d[i] = chr(ord('a') + cnt)\n",
    "                cnt += 1\n",
    "        for i in message:\n",
    "            res += hash_d[i]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        hashmap = {}\n",
    "        index = 0\n",
    "        for k in key:\n",
    "            if k != ' ' and (k not in hashmap):\n",
    "                hashmap[k] = chr(ord('a')+index)\n",
    "                index += 1\n",
    "        result = []\n",
    "        for c in message:\n",
    "            if c == ' ':\n",
    "                result.append(c)\n",
    "            else:\n",
    "                result.append(hashmap[c])\n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        hashMap = dict()\n",
    "        idx = 0\n",
    "        for ch in key:\n",
    "            if ch == ' ' or ch in hashMap:\n",
    "                continue\n",
    "            hashMap[ch] = chr(ord('a') + idx)\n",
    "            idx += 1\n",
    "        \n",
    "        return \"\".join([ hashMap[ch] if ch != ' ' else ' ' for ch in message ])\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        cur = \"a\"\n",
    "        rules = dict()\n",
    "\n",
    "        for c in key:\n",
    "            if c != \" \" and c not in rules:\n",
    "                rules[c] = cur\n",
    "                cur = chr(ord(cur) + 1)\n",
    "\n",
    "        ans = \"\".join(rules.get(c, \" \") for c in message)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        d={}\n",
    "        i=97\n",
    "        for j in range(len(key)):\n",
    "            if key[j] not in d.values() and not key[j].isspace():\n",
    "                d[chr(i)]=key[j]\n",
    "                i+=1\n",
    "        #print(d)\n",
    "        dt={v:k for k,v in d.items()}\n",
    "        ot=\"\"\n",
    "        for i in message:\n",
    "            if i.isspace():\n",
    "                ot+=i\n",
    "            else:\n",
    "                ot+=dt[i]\n",
    "        return ot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        keys = {}\n",
    "        start = 97\n",
    "        index = 0\n",
    "        for c in key:\n",
    "            if c == ' ':\n",
    "                continue\n",
    "            if c not in keys:\n",
    "                keys[c] = chr(start + index) \n",
    "                index += 1\n",
    "        \n",
    "        result = \"\"\n",
    "        for i in range(len(message)):\n",
    "            m = message[i]\n",
    "            if m == ' ':\n",
    "                result += m\n",
    "                continue\n",
    "            result += keys[m]\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        key = key.replace(' ','')\n",
    "        dic = {' ':0}\n",
    "        v = 1\n",
    "        ans =''\n",
    "        for k in key:\n",
    "            if k not in dic:\n",
    "                dic[k] = v\n",
    "                v +=1\n",
    "        lst = [' ']\n",
    "        for l in range(ord('a'),ord('z')+1):\n",
    "            lst += chr(l)\n",
    "        \n",
    "        for i in message:\n",
    "            ans += lst[dic[i]]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        d={}\n",
    "        i=97\n",
    "        j=0\n",
    "        while j<len(key):\n",
    "            if key[j] not in d.values() and not key[j].isspace():\n",
    "                d[chr(i)]=key[j]\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        #print(d)\n",
    "        dt={v:k for k,v in d.items()}\n",
    "        ot=\"\"\n",
    "        for i in message:\n",
    "            if i.isspace():\n",
    "                ot+=i\n",
    "            else:\n",
    "                ot+=dt[i]\n",
    "        return ot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        map=dict()\n",
    "        cur=\"a\"\n",
    "        for i in key:\n",
    "            if i!=\" \" and i not in map:\n",
    "                map[i]=cur\n",
    "                cur=chr(ord(cur)+1)\n",
    "        ans=\"\".join(map.get(i,\" \") for i in message)\n",
    "        return ans    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        i = 97\n",
    "        ma = {' ': ' '}\n",
    "        key = key.replace(' ','')\n",
    "        for k in key:\n",
    "\n",
    "            if k not in ma.keys():\n",
    "                ma[k] = chr(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                continue\n",
    "        # print(ma)\n",
    "        ans = ''\n",
    "        for s in message:\n",
    "\n",
    "            v = ma[s]\n",
    "            ans += v\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        tag = {\" \": \" \"}\n",
    "        stand = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        stand_index = 0\n",
    "        for k in key:\n",
    "            if k not in tag:\n",
    "                tag[k] = stand[stand_index]\n",
    "                stand_index += 1\n",
    "        ans = \"\"\n",
    "        for m in message:\n",
    "            ans += tag[m]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dic = {\" \": \" \"}\n",
    "        i = 0\n",
    "        for c in key:\n",
    "            if c not in dic:\n",
    "                dic[c] = chr(ord(\"a\") + i)\n",
    "                i += 1\n",
    "        return \"\".join([dic[c] for c in message])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        hash_d = {' ':' '}\n",
    "        cnt = 0\n",
    "        res = ''\n",
    "        for i in key:\n",
    "            if i not in hash_d:\n",
    "                hash_d[i] = chr(ord('a') + cnt)\n",
    "                cnt += 1\n",
    "        for i in message:\n",
    "            res += hash_d[i]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        mp = {' ':' '} #提前给空格mapping,减少判断\n",
    "        j=0\n",
    "        for i in key:\n",
    "            if i not in mp:\n",
    "                mp[i]=chr(ord('a')+j)\n",
    "                j+=1\n",
    "        return ''.join(mp[c] for c in message)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dic = {}\n",
    "        i = 0\n",
    "        for c in key:\n",
    "            if c == \" \":\n",
    "                continue\n",
    "            if c not in dic:\n",
    "                dic[c] = i\n",
    "                i += 1\n",
    "        ans = \"\"\n",
    "        for c in message:\n",
    "            if c == \" \":\n",
    "                ans += c\n",
    "            else:\n",
    "                ans += chr(dic[c] + 97)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        d = {}\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while len(d) != 26 and i + j != len(key):\n",
    "            if key[i + j] != \" \":\n",
    "                if key[i + j] not in d.keys():\n",
    "                    d[key[i + j]] = chr(i + 97)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        l = ''\n",
    "        for i in message:\n",
    "            if i != \" \":\n",
    "                l += d[i]\n",
    "            else:\n",
    "                l += i\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        cur = \"a\"\n",
    "        rules = dict()\n",
    "\n",
    "        for c in key:\n",
    "            if c != \" \" and c not in rules:\n",
    "                rules[c] = cur\n",
    "                cur = chr(ord(cur) + 1)\n",
    "\n",
    "        ans = \"\".join(rules.get(c, \" \") for c in message)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        pwtable = dict()\n",
    "        alphabet = [chr(i) for i in range(ord(\"a\"),ord(\"z\")+1)]\n",
    "        n = 0\n",
    "        print(alphabet)\n",
    "        for i in key:\n",
    "            if i != \" \" and i not in pwtable.keys():\n",
    "                print([i])\n",
    "                pwtable[i] = alphabet[n]\n",
    "                n += 1\n",
    "        messagestr = \"\"\n",
    "        for i in message:\n",
    "            if i == \" \":\n",
    "                messagestr = messagestr + i\n",
    "            elif i in pwtable.keys():\n",
    "                messagestr = messagestr + pwtable[i]\n",
    "        return messagestr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        mp = {' ': ' '}\n",
    "        i = 0\n",
    "        for c in key:\n",
    "            if c not in mp:\n",
    "                mp[c] = ascii_lowercase[i]\n",
    "                i += 1\n",
    "        return ''.join(mp[c] for c in message)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        key=key.split()\n",
    "        key2=key3=\"\"\n",
    "        for i in key:\n",
    "            key2+=i\n",
    "        for i in key2:\n",
    "            if i not in key3:\n",
    "                key3+=i   \n",
    "        def func1(a:str)->str:\n",
    "            if a==\" \":\n",
    "                return \" \"\n",
    "            for i in range(26):\n",
    "                if ord(a)==ord(key3[i]):\n",
    "                    return chr(ord(\"a\")+i)\n",
    "        message2=\"\"\n",
    "        for i in message:\n",
    "            x=func1(i)\n",
    "            message2=message2+x\n",
    "        return message2\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        mapper = {' ': ' '}\n",
    "        i = 0\n",
    "        for ch in key:\n",
    "            if ch not in mapper:\n",
    "                mapper[ch] = chr(ord('a') + i)\n",
    "                i += 1\n",
    "        return ''.join(mapper[ch] for ch in message)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dic = {}\n",
    "        for ch in key:\n",
    "            if ch!=\" \" and ch not in dic:\n",
    "                dic[ch] = len(dic)\n",
    "        \n",
    "        ans = \"\"\n",
    "        for ch in message:\n",
    "            if ch.isalpha():\n",
    "                ans += chr( dic[ch] + ord(\"a\") )\n",
    "            else:\n",
    "                ans += ch \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dict0 = dict()\n",
    "        res = ''\n",
    "        dict0[' '] = ' '\n",
    "        key0 = key.replace(' ', '')\n",
    "        # print(key0)\n",
    "        char_now = 'a'\n",
    "        dict0[key0[0]] = char_now\n",
    "        for i in range(len(key0)):\n",
    "            if key0[i] not in dict0:\n",
    "                char_now = chr(ord(char_now) + 1)\n",
    "                dict0[key0[i]] = char_now\n",
    "        # print(dict0)\n",
    "        for m in message:\n",
    "            res += dict0[m]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        key_dict = {' ':' '}\n",
    "        char = 'a'\n",
    "        # 获取key首字母排序并使key_list与字母表组成字典\n",
    "        for i in range(len(key)):\n",
    "            if key[i] != ' ' and (key[i] not in key[0:i]):\n",
    "                key_dict[key[i]] = char\n",
    "                char = chr(ord(char)+1)\n",
    "        ret = []\n",
    "        for i in message:\n",
    "            ret += key_dict[i]\n",
    "        return ''.join(ret)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        table = {}\n",
    "        res = \"\"\n",
    "        for c in key:\n",
    "            if c == \" \" or c in table:\n",
    "                continue\n",
    "            \n",
    "            else:\n",
    "                table[c] = chr(ord('a') + len(table))\n",
    "\n",
    "        for c in message:\n",
    "            if c == \" \":\n",
    "                res += c\n",
    "            else:\n",
    "                res += table[c]\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        # 构建替换字典\n",
    "        dic = dict()\n",
    "        count = 0\n",
    "        for i in range(0, len(key)):\n",
    "            if count == 26:\n",
    "                break\n",
    "            if key[i] == ' ':\n",
    "                continue\n",
    "            if key[i] not in dic:\n",
    "                dic[key[i]] = chr(ord('a') + count)\n",
    "                count += 1\n",
    "        # 执行替换\n",
    "        res = ''\n",
    "        for i in range(0, len(message)):\n",
    "            if message[i] == ' ':\n",
    "                res += ' '\n",
    "            else:\n",
    "                res += dic[message[i]]\n",
    "\n",
    "        # for i in range(0, len(dic)):\n",
    "        #     c = chr(ord('a') + i)\n",
    "        #     if c in dic:\n",
    "        #         message.replace(c, dic[c])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        hash_d = {' ':' '}\n",
    "        cnt = 0\n",
    "        res = ''\n",
    "        for i in key:\n",
    "            if i not in hash_d:\n",
    "                hash_d[i] = chr(ord('a') + cnt)\n",
    "                cnt += 1\n",
    "        for i in message:\n",
    "            res += hash_d[i]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dic ={}\n",
    "        res=[]\n",
    "        for i in key:\n",
    "            if i!=' ':\n",
    "                res.append(i)\n",
    "        index=0\n",
    "        for string in res:\n",
    "            if string==' ':\n",
    "                continue\n",
    "            elif string in dic:\n",
    "                continue\n",
    "            else:\n",
    "                dic[string]=chr(ord('a')+index)\n",
    "                index+=1\n",
    "        t=list(message)\n",
    "        for i in range(len(t)):\n",
    "            if i==' ':\n",
    "                continue\n",
    "            else:\n",
    "                if t[i] in dic:\n",
    "                    t[i]=dic[t[i]]\n",
    "        return ''.join(t) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        cur = \"a\"\n",
    "        rules = dict()\n",
    "\n",
    "        for c in key:\n",
    "            if c != \" \" and c not in rules:\n",
    "                rules[c] = cur\n",
    "                cur = chr(ord(cur) + 1)\n",
    "\n",
    "        ans = \"\".join(rules.get(c, \" \") for c in message)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        i = 0\n",
    "        d = {' ': ' '}\n",
    "        for k in key:\n",
    "            if k not in d:\n",
    "                d[k] = alphabet[i]\n",
    "                i+=1\n",
    "        return ''.join([d[i] for i in message])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        mp, curr = {}, 97\n",
    "        for c in key:\n",
    "            if c != ' ' and c not in mp:\n",
    "                mp[c] = chr(curr)\n",
    "                curr += 1\n",
    "        return \"\".join(mp.get(c, ' ') for c in message)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        key=key.split()\n",
    "        key2=key3=\"\"\n",
    "        for i in key:\n",
    "            key2+=i\n",
    "        for i in key2:\n",
    "            if i not in key3:\n",
    "                key3+=i   \n",
    "        def func1(a:str)->str:\n",
    "            if a==\" \":\n",
    "                return \" \"\n",
    "            for i in range(26):\n",
    "                if ord(a)==ord(key3[i]):\n",
    "                    return chr(ord(\"a\")+i)\n",
    "        message2=\"\"\n",
    "        for i in message:\n",
    "            x=func1(i)\n",
    "            message2=message2+x\n",
    "        return message2\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        stack = []\n",
    "        for i in key:\n",
    "            if i not in stack and i != ' ' and len(stack) < 26:\n",
    "                stack.append(i)\n",
    "        dic = {}\n",
    "        for j in range(0,26):\n",
    "            dic[stack[j]] = chr(97+j)\n",
    "        # return dic\n",
    "        res = ''\n",
    "        for m in message:\n",
    "            if m != ' ':\n",
    "                res += dic[m]\n",
    "            else:\n",
    "                res += ' '\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        d = {\" \": \" \"}\n",
    "        i = 0\n",
    "        for c in key:\n",
    "            if c not in d:\n",
    "                d[c] = ascii_lowercase[i]\n",
    "                i += 1\n",
    "        return \"\".join(d[c] for c in message)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        output_list = []\n",
    "        \n",
    "        newkey=''\n",
    "        for char in key:\n",
    "            if char not in newkey:\n",
    "                newkey+=char\n",
    "        \n",
    "        qq=\"\".join(newkey.split(\" \"))\n",
    "        newqq=list(qq)\n",
    "        value=[\"a\",\"b\",\"c\",\"d\",\"e\",\"f\",\"g\",\"h\",\"i\",\"j\",\"k\",\"l\",\"m\",\"n\",\"o\",\"p\",\"q\",\"r\",\"s\",\"t\",\"u\",\"v\",\"w\",\"x\",\"y\",\"z\"]\n",
    "        dict1=dict(zip(newqq,value))\n",
    "        dict1[\" \"]=\" \"\n",
    "        newmessage=list(message)\n",
    "\n",
    "        for ww in newmessage:\n",
    "            output_list.append(dict1[ww]) \n",
    "        return \"\".join(output_list)\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        d = {}\n",
    "        i = 97\n",
    "        for c in key:\n",
    "            if c == \" \":\n",
    "                continue\n",
    "            if c not in d:\n",
    "                d[c] = chr(i) \n",
    "                i += 1\n",
    "        m = list(message)\n",
    "        for i, c in enumerate(m):\n",
    "            if c != \" \":\n",
    "                m[i] = d[c]\n",
    "        return \"\".join(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        dic={}\n",
    "        ans=set()\n",
    "        index=ord('a')\n",
    "        for k in key:\n",
    "            if k==\" \" or k in ans:\n",
    "                continue\n",
    "            dic[k]=chr(index)\n",
    "            ans.add(k)\n",
    "            index+=1\n",
    "        res=\"\"\n",
    "        for m in message:\n",
    "            res+=dic.get(m,' ')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        cur = \"a\"\n",
    "        rules = dict()\n",
    "\n",
    "        for c in key:\n",
    "            if c != \" \" and c not in rules:\n",
    "                rules[c] = cur\n",
    "                cur = chr(ord(cur) + 1)\n",
    "\n",
    "        ans = \"\".join(rules.get(c, \" \") for c in message)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        char_dx = {i - 65: chr(i).lower() for i in range(ord('A'), ord('Z') + 1)}\n",
    "        msg_dic = {}\n",
    "        num = 0\n",
    "        for s in key:\n",
    "            if s in msg_dic or s == ' ':\n",
    "                continue\n",
    "            msg_dic[s] = char_dx[num]\n",
    "            num += 1\n",
    "\n",
    "        new_msg = ''\n",
    "        for s in message:\n",
    "            if s != ' ':\n",
    "                s = msg_dic[s]\n",
    "            new_msg += s\n",
    "\n",
    "        return new_msg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        fkey = []\n",
    "        key = key.replace(\" \",\"\")\n",
    "        for c in key:\n",
    "            if c not in fkey:\n",
    "                fkey.append(c)\n",
    "        codebooks = dict(zip(fkey,\"abcdefghijklmnopqrstuvwxyz\"))\n",
    "        decode =\"\"\n",
    "        print(codebooks)\n",
    "        for c in message:\n",
    "            if c == \" \":\n",
    "                decode += \" \"\n",
    "            else:\n",
    "                decode += codebooks[c]\n",
    "        return decode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        map_key = {' ': ' '}\n",
    "        cnt = 0\n",
    "        for i in range(len(key)):\n",
    "            char = key[i]\n",
    "            if char in map_key.keys() or not(ord('a') <= ord(char) <= ord('z')):\n",
    "                continue\n",
    "            map_key[char] = chr(ord('a') + cnt)\n",
    "            cnt += 1\n",
    "\n",
    "        # 第二种返回方式\n",
    "        return ''.join(map_key[i] for i in message)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        alpbt = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        keytrim = ''\n",
    "        for l in key:\n",
    "            if l not in keytrim and l != ' ':\n",
    "                keytrim += l\n",
    "        for l in alpbt:\n",
    "            if l not in keytrim:\n",
    "                keytrim += l\n",
    "        result = ''\n",
    "        for l in message:\n",
    "            if l == ' ':\n",
    "                result += ' '\n",
    "            else:\n",
    "                result += alpbt[keytrim.index(l)]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        origional = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        key_message = ''\n",
    "        dict = {}\n",
    "        for each_cha in key:\n",
    "            if each_cha == ' ':\n",
    "                continue\n",
    "            if each_cha not in key_message:\n",
    "                key_message += each_cha\n",
    "        for each_cha in key_message:\n",
    "            index_each = key_message.index(each_cha)\n",
    "            dict[each_cha] = origional[index_each]\n",
    "        result = ''\n",
    "        decode_cha = ''\n",
    "        for each_cha in message:\n",
    "            if each_cha == ' ':\n",
    "                decode_cha = ' '\n",
    "            else:\n",
    "                decode_cha = dict[each_cha]\n",
    "            result += decode_cha\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        rules = dict()\n",
    "        cur = \"a\"\n",
    "        for c in key:\n",
    "            if c != \" \" and c not in rules:\n",
    "                rules[c] = cur\n",
    "                cur = chr(ord(cur) + 1)\n",
    "        ans =\"\".join(rules.get(c,\" \") for c in message)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeMessage(self, key: str, message: str) -> str:\n",
    "        abc = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        secrets = dict()\n",
    "        secrets[\" \"] = \" \"\n",
    "        i = 0\n",
    "        for k in key:\n",
    "            if k == \" \":\n",
    "                continue\n",
    "            if k not in secrets:\n",
    "                secrets[k] = abc[i]\n",
    "                i += 1\n",
    "            if i >= 26:\n",
    "                break\n",
    "        ans = []\n",
    "        for ch in message:\n",
    "            ans.append(secrets[ch])\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        if rows == 1:\n",
    "            return encodedText\n",
    "        ans = ''\n",
    "        for j in range(cols):\n",
    "            i = 0\n",
    "            while i<rows and j <cols:\n",
    "                ans += encodedText[i * cols + j]\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return ans.rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        col = len(encodedText)//rows\n",
    "        # def zuibiao(index):\n",
    "        #     return index//col,index%col\n",
    "        def zuibiao2index(x,y):\n",
    "            return x*col + y \n",
    "        # 差值是从0，到col-row的\n",
    "        def traverse(cha):\n",
    "            res = ''\n",
    "            for i in range(rows):\n",
    "                x = i \n",
    "                y = i+cha\n",
    "                index = zuibiao2index(x,y)\n",
    "                if index < len(encodedText):\n",
    "                    res += encodedText[index]\n",
    "                else:\n",
    "                    return res\n",
    "\n",
    "        res = ''\n",
    "        for cha in range(col+1):\n",
    "            for i in range(rows):\n",
    "                x = i \n",
    "                y = i+cha\n",
    "                index = zuibiao2index(x,y)\n",
    "                if index < len(encodedText):\n",
    "                    res += encodedText[index]\n",
    "                else:\n",
    "                    return res.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        ans = ''\n",
    "        n = len(encodedText)\n",
    "        nc = n - encodedText.count(\" \")\n",
    "        cols = n // rows\n",
    "\n",
    "        for j in range(cols):\n",
    "            i = 0\n",
    "            while 0 <= i < rows and 0 <= j < cols and nc:\n",
    "                ans += encodedText[i*cols+j]\n",
    "                if encodedText[i*cols+j].isalpha():\n",
    "                    nc -= 1\n",
    "                i += 1\n",
    "                j += 1\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        length = len(encodedText)\n",
    "        col = int(length / rows)\n",
    "        s = ''\n",
    "        for j in range(col):\n",
    "            for i in range(rows):\n",
    "                if (index := i * col + j + i) < length:\n",
    "                    s += encodedText[index]\n",
    "        return s.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, text: str, m: int) -> str:\n",
    "        l = len(text)\n",
    "        n = l // m\n",
    "        ans = ''\n",
    "        for start in range(n):\n",
    "            for i in range(start, l, n+1):\n",
    "                ans += text[i]\n",
    "        return ans.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        result=''\n",
    "        cols=len(encodedText)//rows\n",
    "        for i in range(cols):\n",
    "            j=0\n",
    "            while j<rows and j+i<cols:\n",
    "                result+=encodedText[(cols+1)*j+i]\n",
    "                j+=1\n",
    "        return result.rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        cols = n // rows\n",
    "        result = ''\n",
    "        for j in range(cols):\n",
    "            x = j\n",
    "            while(x < n):\n",
    "                result += encodedText[x]\n",
    "                x += 1 + cols\n",
    "        return result.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        col = len(encodedText)//rows\n",
    "        def zuibiao2index(x,y):\n",
    "            return x*col + y \n",
    "        res = ''\n",
    "        for cha in range(col+1):\n",
    "            for i in range(rows):\n",
    "                x = i \n",
    "                y = i+cha\n",
    "                index = zuibiao2index(x,y)\n",
    "                if index < len(encodedText):\n",
    "                    res += encodedText[index]\n",
    "                else:\n",
    "                    return res.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        total = len(encodedText)\n",
    "        columns = total // rows\n",
    "        s = ''\n",
    "        for j in range(columns):\n",
    "            for i in range(min(rows, columns - j)):\n",
    "                s += encodedText[i * columns + i + j]\n",
    "        return s.rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        ans = ''\n",
    "        i, j, k, cols = 0, 0, 0, len(encodedText) // rows\n",
    "        while k < cols:\n",
    "            ans += encodedText[i * cols + j]\n",
    "            i += 1\n",
    "            j += 1 \n",
    "            if i == rows or j == cols:\n",
    "                k += 1\n",
    "                i, j = 0, k\n",
    "        return ans.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        cols = n // rows\n",
    "        result = ''\n",
    "        for j in range(cols):\n",
    "            x = j\n",
    "            while(x < n):\n",
    "                result += encodedText[x]\n",
    "                x += 1 + cols\n",
    "        return result.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        flag = len(encodedText)\n",
    "        #print(\"asdf->>>\",flag)\n",
    "        m = flag // rows\n",
    "        res = ''\n",
    "        for i in range(m):\n",
    "            for j in range(rows):\n",
    "                #print(encodedText[j * m + i+j],j * m + i+j)\n",
    "                if j*m+i+j>=flag:\n",
    "                    break\n",
    "                #print(encodedText[j * m + i+j])\n",
    "                res += encodedText[j * m + i+j]\n",
    "        ff  =0\n",
    "        for i in range(len(res)-1,-1,-1):\n",
    "            if res[i]!=' ':\n",
    "                ff = i\n",
    "                break\n",
    "        return res[:ff+1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, text: str, m: int) -> str:\n",
    "        l = len(text)\n",
    "        n = l // m\n",
    "        ans = ''\n",
    "        for start in range(n-m+2):\n",
    "            for i in range(start, l, n+1):\n",
    "                ans += text[i]\n",
    "        return ans.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        length = len(encodedText)\n",
    "        col = int(length / rows)\n",
    "        s = ''\n",
    "        for j in range(col):\n",
    "            for i in range(rows):\n",
    "                index = i * col + j + i\n",
    "                if index < length:\n",
    "                    s += encodedText[index]\n",
    "        return s.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        if encodedText=='':\n",
    "            return ''\n",
    "        c=len(encodedText)//rows\n",
    "        ans=''\n",
    "        for i in range(c):\n",
    "            ans=ans+encodedText[i::c+1]\n",
    "        i=len(ans)-1\n",
    "        while ans[i]==' ':\n",
    "            i-=1\n",
    "        return ans[:i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        ans = ''\n",
    "        i, j, k, cols = 0, 0, 0, len(encodedText) // rows\n",
    "        while k < cols:\n",
    "            ans += encodedText[i * cols + j]\n",
    "            i += 1\n",
    "            j += 1 \n",
    "            if i == rows or j == cols:\n",
    "                k += 1\n",
    "                i, j = 0, k\n",
    "        return ans.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText)//rows\n",
    "        ret = \"\"\n",
    "        for c in range(cols):\n",
    "            for r in range(rows):\n",
    "                #获取r,c+r的字符\n",
    "                if c+r>=cols:\n",
    "                    break\n",
    "                ret += encodedText[r*cols+c+r]\n",
    "        \n",
    "        return ret.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        m = rows\n",
    "        nn = len(encodedText)\n",
    "        n = nn // m\n",
    "        ans = ''\n",
    "        for j in range(n):\n",
    "            idx = j\n",
    "            for i in range(m):\n",
    "                if i * n + idx >= nn:\n",
    "                    break\n",
    "                ans += encodedText[i * n + idx]\n",
    "                idx += 1\n",
    "\n",
    "        return ans.rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        c=len(encodedText)//rows\n",
    "        k = 0\n",
    "        s = ''\n",
    "        while 1:\n",
    "            i = 0\n",
    "            j = k\n",
    "            while i < rows:\n",
    "                x = i*c+j\n",
    "                i += 1\n",
    "                j += 1\n",
    "                if x >= len(encodedText):\n",
    "                    return s.rstrip()\n",
    "                s += encodedText[x]\n",
    "            k += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        # m, n = rows, len(encodedText) // rows\n",
    "        # ans = []\n",
    "        # for j in range(n):\n",
    "        #     if encodedText[0][j] == ' ':\n",
    "        #         break\n",
    "        #     for i in range(m):\n",
    "        #         if j + i < n:\n",
    "        #             ans.append(encodedText[i][j + i])\n",
    "        #         else:\n",
    "        #             break\n",
    "        # return ' '.join(ans)\n",
    "        m, n = rows, len(encodedText) // rows\n",
    "        ans = []\n",
    "        for j in range(n - m + 2):\n",
    "            for i in range(m):\n",
    "                if j + i < n:\n",
    "                    ans.append(encodedText[i*n + j + i])\n",
    "                else:\n",
    "                    break\n",
    "        return ''.join(ans).rstrip()\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        width = w = cols - (rows - 1)\n",
    "        if cols == 0: return ''\n",
    "        r = []\n",
    "        for i in range(rows):\n",
    "            for j in range(i * cols + i + w, i * cols + cols):\n",
    "                if encodedText[j] != ' ':\n",
    "                    width = max(width, j - (i * cols + i) + 1)\n",
    "        for i in range(rows):\n",
    "            r.append(encodedText[i * cols + i: i * cols + i + width])\n",
    "            if len(r[-1]) < width:\n",
    "                r[-1] = r[-1] + ' ' * (width - len(r[-1]))\n",
    "        # print(r)\n",
    "        ans = [''.join(x) for x in zip(*r)]\n",
    "        return ''.join(ans).rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows   # 辅助矩阵的列数\n",
    "        res = []   # 遍历到的字符\n",
    "        for i in range(cols):\n",
    "            # 从左至右枚举每一条路径\n",
    "            r = 0\n",
    "            c = i\n",
    "            while r < rows and c < cols:\n",
    "                res.append(encodedText[r*cols+c])\n",
    "                r += 1\n",
    "                c += 1\n",
    "        # 删去末尾空格\n",
    "        while res and res[-1] == ' ':\n",
    "            res.pop()\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols=len(encodedText)//rows\n",
    "        res =[]\n",
    "        for i in range(cols):\n",
    "            r=0\n",
    "            c=i\n",
    "            while r<rows and c<cols:\n",
    "                res.append(encodedText[r*cols+c])\n",
    "                r+=1\n",
    "                c+=1\n",
    "        while res and res[-1]==' ':\n",
    "            res.pop()\n",
    "        return \"\".join(res)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        m, n = rows, len(encodedText) // rows\n",
    "        ans = []\n",
    "        for j in range(n - m + 2):\n",
    "            for i in range(m):\n",
    "                if j + i < n:\n",
    "                    ans.append(encodedText[i*n + j + i])  # encodedText[i][j + i]\n",
    "        return ''.join(ans).rstrip()\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows   # 辅助矩阵的列数\n",
    "        res = []   # 遍历到的字符\n",
    "        for i in range(cols):\n",
    "            # 从左至右枚举每一条路径\n",
    "            r = 0\n",
    "            c = i\n",
    "            while r < rows and c < cols:\n",
    "                res.append(encodedText[r*cols+c])\n",
    "                r += 1\n",
    "                c += 1\n",
    "        # 删去末尾空格\n",
    "        while res and res[-1] == ' ':\n",
    "            res.pop()\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        width = cols\n",
    "        if cols == 0: return ''\n",
    "        r = []\n",
    "        for i in range(rows):\n",
    "            r.append(encodedText[i * cols + i: i * cols + cols])\n",
    "            if len(r[-1]) < width:\n",
    "                r[-1] = r[-1] + ' ' * (width - len(r[-1]))\n",
    "        ans = [''.join(x) for x in zip(*r)]\n",
    "        return ''.join(ans).rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        if cols == 0: return ''\n",
    "        r = []\n",
    "        for i in range(rows):\n",
    "            r.append(encodedText[i * cols + i: i * cols + cols])\n",
    "            if len(r[-1]) < cols:\n",
    "                r[-1] = r[-1] + ' ' * (cols - len(r[-1]))\n",
    "        ans = [''.join(x) for x in zip(*r)]\n",
    "        return ''.join(ans).rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        cols = len(encodedText) // rows\n",
    "        mat = [[' '] * cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                mat[i][j] = encodedText[cols * i + j]\n",
    "\n",
    "        decoded = \"\"\n",
    "        for start in range(cols):\n",
    "            r, c = 0, start\n",
    "            while r < rows and c < cols:\n",
    "                decoded += mat[r][c]\n",
    "                r += 1; c += 1\n",
    "\n",
    "        return decoded.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        n = len(encodedText)\n",
    "        cols = n // rows\n",
    "        metric = [[encodedText[c] for c in range(i * cols, cols + i*cols)] for i in range(rows) ]\n",
    "        #print(metric)\n",
    "        res = ''\n",
    "        x = 0\n",
    "        flag = True\n",
    "        while x < cols and flag:\n",
    "            for i in range(rows):\n",
    "                if x + i == cols:\n",
    "                    flag = False\n",
    "                    break \n",
    "                res += metric[i][i + x]\n",
    "            x += 1\n",
    "        \n",
    "        return res.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, en: str, rows: int) -> str:\n",
    "        n = len(en)\n",
    "        col = n // rows\n",
    "        v = []\n",
    "      \n",
    "        l = 0\n",
    "        \n",
    "        while l < n:\n",
    "            v.append(en[l:l + col])\n",
    "            l += col\n",
    "        x,y = 0,0\n",
    "        tmp = []\n",
    "        while y < col:\n",
    "            cx,cy = 0,y\n",
    "            while cx < rows and cy < col:\n",
    "                 \n",
    "                 tmp.append(v[cx][cy])\n",
    "                 cx += 1\n",
    "                 cy += 1\n",
    "            y += 1\n",
    "        return ''.join(tmp).rstrip(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def decodeCiphertext(self, encodedText, rows):\n",
    "        cols, lentext = len(encodedText) // rows, len(encodedText)\n",
    "        return ''.join(encodedText[j] for i in range(cols) for j in range(i, lentext, cols + 1)).rstrip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def decodeCiphertext(self, encodedText, rows):\n",
    "        cols, lentext = len(encodedText) // rows, len(encodedText)\n",
    "        return ''.join(encodedText[j] for i in range(cols) for j in range(i, lentext, cols + 1)).rstrip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "      n = len(encodedText) \n",
    "      cols = int(n // rows)\n",
    "      return ''.join(encodedText[j] for i in range(cols) for j in range(i, n, cols + 1)).rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        width = len(encodedText) // rows \n",
    "        matrix = [ [''] * width for _ in range(rows)]\n",
    "        i, j = 0, 0\n",
    "        for ch in encodedText:\n",
    "            matrix[i][j] = ch\n",
    "            j += 1\n",
    "            if j >= width:\n",
    "                j = 0 \n",
    "                i += 1\n",
    "        res = []\n",
    "        for j in range(width):\n",
    "            i = 0\n",
    "            while i < rows and j < width:\n",
    "                res.append( matrix[i][j] )\n",
    "                i += 1\n",
    "                j += 1\n",
    " \n",
    "        while res and res[-1] == \" \":\n",
    "            res.pop()                \n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        if not encodedText or rows == 1:\n",
    "            return encodedText\n",
    "        length = len(encodedText) // rows\n",
    "        square = [[' ' for i in range(length + 1)] for j in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(length):\n",
    "                square[i][j] = encodedText[i*length + j]\n",
    "        #print(square)\n",
    "        res = []\n",
    "        x = 0\n",
    "        y = 0\n",
    "        while True:\n",
    "            res.append(square[x][y])\n",
    "            if x == rows - 1 or y == length - 1:\n",
    "                y = abs(x-y)+1\n",
    "                x = 0\n",
    "            else:\n",
    "                x += 1\n",
    "                y += 1\n",
    "            if x==0 and y == length:\n",
    "                break\n",
    "        print(\"res:\", res)\n",
    "        r = ''\n",
    "        for i in range(len(res)-1, -1, -1):\n",
    "            if res[i] != ' ':\n",
    "                break\n",
    "            else:\n",
    "                res.pop()\n",
    "        \n",
    "        for i in res:\n",
    "            r = r + str(i)\n",
    "        return r\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "        len_enc = len(encodedText)\n",
    "        if rows == 1:\n",
    "            return encodedText.rstrip()\n",
    "        if len_enc == 0:\n",
    "            return ''\n",
    "        lie = len_enc//rows\n",
    "        biao = [[]]*rows\n",
    "        biao_1 =list(encodedText)\n",
    "        a = ''\n",
    "        for i in range(rows):\n",
    "            biao[i]= biao[i]+biao_1[i*(lie):(i+1)*lie]\n",
    "        biao_2 = []\n",
    "        for i in range(rows):\n",
    "            biao_2.append(biao[i][i:]+[' ']*i)\n",
    "        for i in range(len(biao[0])):\n",
    "            for j in range(len(biao_2)):\n",
    "                a = a+biao_2[j][i]\n",
    "        return a.rstrip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "      n = len(encodedText)\n",
    "      if not n:\n",
    "        return encodedText\n",
    "      \n",
    "      cols, ans, last = n / rows, [' '] * n, 0\n",
    "      for i, ch in enumerate(encodedText):\n",
    "        row, col = i // cols, i % cols\n",
    "        if col >= row:\n",
    "          index = int(row + (col - row) * rows)\n",
    "          ans[index] = ch\n",
    "          if ch != ' ':\n",
    "            last = max(last, index)\n",
    "      return ''.join(i for i in ans[:last+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeCiphertext(self, encodedText: str, rows: int) -> str:\n",
    "      n = len(encodedText) \n",
    "      cols, ans, last = n / rows, [' '] * n, 0\n",
    "      for i, ch in enumerate(encodedText):\n",
    "        row, col = i // cols, i % cols\n",
    "        if col >= row:\n",
    "          index = int(row + (col - row) * rows)\n",
    "          ans[index] = ch\n",
    "          if ch != ' ':\n",
    "            last = max(last, index)\n",
    "      return ''.join(i for i in ans[:last+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#解码方法2，\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        #dp[:i]表示0到i上的解码方案数目，dp[i]=c1*dp[i-1]+c2*dp[i-2]\n",
    "        def decode1(c):\n",
    "            if c=='0':return 0\n",
    "            if c=='*':return 9\n",
    "            return 1\n",
    "        def decode2(c1,c2):\n",
    "            if c1=='*'and c2=='*':return 15 #11-19,21-26共15种选择\n",
    "            if c1=='*':\n",
    "                return 2 if c2<='6' else 1\n",
    "            if c2=='*':\n",
    "                if c1=='1':return 9\n",
    "                if c1=='2':return 6\n",
    "                return 0\n",
    "            num=int(c1)*10+int(c2)\n",
    "            if num>=10 and num<=26:return 1\n",
    "            else:return 0\n",
    "        mod=10**9+7\n",
    "        n=len(s)\n",
    "        dp=[0]*(n+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=decode1(s[i-1])*dp[i-1]+((decode2(s[i-2],s[i-1])if i>=2 else 0)*dp[i-2])\n",
    "            dp[i]=dp[i]%mod\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: ####################记忆化搜索\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        n = len(s)\n",
    "        self.memo = [-1] * n \n",
    "\n",
    "        def decodeOneChar(c):\n",
    "            if c == '0': return 0\n",
    "            if c == '*': return 9\n",
    "            return 1\n",
    "        \n",
    "        def decodeTwoChar(c1, c2):\n",
    "            if c1 == '*' and c2 == '*': return 15 # 11,...,19 21,...26\n",
    "            elif c1 == '*':\n",
    "                if c2 <= '6': return 2 # 1 c2, 2 c2\n",
    "                else: return 1 # c2 = 7, c1只能为1\n",
    "            elif c2 == '*':\n",
    "                if c1 == '1': return 9\n",
    "                elif c1 == '2': return 6\n",
    "                else: return 0\n",
    "            else:\n",
    "                twoSum = (ord(c1) - ord('0')) * 10 + ord(c2) - ord('0')\n",
    "                if twoSum >= 10 and twoSum <= 26: return 1\n",
    "                return 0\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n: return 1\n",
    "            if i > n: return 0\n",
    "            if self.memo[i] != -1: return self.memo[i]\n",
    "            #########################注意这里是乘法\n",
    "            ans = decodeOneChar(s[i]) * dfs(i + 1); ans %= MOD\n",
    "            if i + 1 < n:\n",
    "                ans += decodeTwoChar(s[i], s[i + 1]) * dfs(i + 2); ans %= MOD\n",
    "            self.memo[i] = ans\n",
    "            return ans\n",
    "        return dfs(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = {}\n",
    "        base = 10**9 + 7\n",
    "\n",
    "        def decode(i):\n",
    "            if i>n:\n",
    "                return 0\n",
    "            if i==n:\n",
    "                return 1\n",
    "            if s[i] == '0':\n",
    "                return 0\n",
    "            if i in dp:\n",
    "                return dp[i]\n",
    "\n",
    "            ans = 0\n",
    "            if s[i] in '3456789':\n",
    "                ans = decode(i+1)\n",
    "            if s[i] in '1*':\n",
    "                ans = decode(i+1)\n",
    "                if i <= n-2:\n",
    "                    if s[i+1] == '*':\n",
    "                        ans += 9*decode(i+2)\n",
    "                    else:\n",
    "                        ans += decode(i+2)\n",
    "            if s[i] in '2*':\n",
    "                ans += decode(i+1)\n",
    "                if i <= n-2:\n",
    "                    if s[i+1] == '*':\n",
    "                        ans += 6*decode(i+2)\n",
    "                    elif s[i+1] in '0123456':\n",
    "                        ans += decode(i+2)\n",
    "            if s[i] == '*':\n",
    "                ans += 7*decode(i+1)\n",
    "            \n",
    "            ans = ans%base\n",
    "            dp[i] = ans\n",
    "            return ans\n",
    "\n",
    "        return decode(0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded.insert(0, first)\n",
    "        for i in range(1, len(encoded)):\n",
    "            encoded[i] ^= encoded[i-1]\n",
    "        return encoded"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: list[int], first: int) -> list[int]:\n",
    "        for i,v in enumerate(encoded):\n",
    "            encoded[i] = first\n",
    "            first = v ^ first\n",
    "        encoded.append(first)\n",
    "        return encoded\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded[0] = first ^ encoded[0]\n",
    "        for i in range(len(encoded)-1):\n",
    "            encoded[i+1] ^= encoded[i]\n",
    "        return [first] + encoded\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded[0] = first ^ encoded[0]\n",
    "        for i in range(len(encoded)-1):\n",
    "            encoded[i+1] ^= encoded[i]\n",
    "        return [first] + encoded\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: list[int], first: int) -> list[int]:\n",
    "        for i,v in enumerate(encoded):\n",
    "            encoded[i] = first\n",
    "            first = v ^ first\n",
    "        encoded.append(first)\n",
    "        return encoded\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded.insert(0,first)\n",
    "        for i in range(1,len(encoded)):\n",
    "            encoded[i] = encoded[i-1] ^ encoded[i]\n",
    "        return encoded"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded[0] = first ^ encoded[0]\n",
    "        for i in range(len(encoded)-1):\n",
    "            encoded[i+1] ^= encoded[i]\n",
    "        return [first] + encoded\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded.insert(0,first)\n",
    "        for i in range(1,len(encoded)):\n",
    "            encoded[i] = encoded[i-1] ^ encoded[i]\n",
    "        return encoded"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded[0] = first ^ encoded[0]\n",
    "        for i in range(len(encoded)-1):\n",
    "            encoded[i+1] ^= encoded[i]\n",
    "        return [first] + encoded\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        ans = [0] * n\n",
    "        ans[0] = first\n",
    "\n",
    "        for i in range(1, n):\n",
    "            ans[i] = ans[i-1] ^ encoded[i-1]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded[0] = first ^ encoded[0]\n",
    "        for i in range(len(encoded)-1):\n",
    "            encoded[i+1] ^= encoded[i]\n",
    "        return [first] + encoded\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        encoded[0] = first ^ encoded[0]\n",
    "        for i in range(len(encoded)-1):\n",
    "            encoded[i+1] = encoded[i] ^ encoded[i+1]\n",
    "        return [first] + encoded\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        n=len(encoded)+1\n",
    "        result=[0]*n\n",
    "        result[0]=first\n",
    "        for i in range(1,n):\n",
    "            result[i]=encoded[i-1]^result[i-1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        res = [first]\n",
    "        for i in range(len(encoded)):\n",
    "            res.append(encoded[i]^res[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        n = len(encoded)+1\n",
    "        arr = [first]*n\n",
    "        for i in range(1,n):\n",
    "            arr[i] = arr[i-1]^encoded[i-1]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        l =  len(encoded)\n",
    "        arr= [first] + [0] * l\n",
    "\n",
    "        for i in range(1,l+1):\n",
    "            arr[i] = arr[i-1] ^ encoded[i-1]\n",
    "\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        n=len(encoded)+1\n",
    "        arr=[None]*n\n",
    "        arr[0]=first\n",
    "        for i in range(n-1):\n",
    "            arr[i+1]=arr[i]^encoded[i]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#a^b=c,则a=b^c\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr=[0]*(len(encoded)+1)\n",
    "        arr[0]=first\n",
    "\n",
    "        for i in range(0,len(encoded)):\n",
    "             arr[i + 1] = arr[i]^encoded[i]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        ans = [first] * (1 + len(encoded))\n",
    "        for i in range(len(ans) - 1):\n",
    "            ans[i + 1] = xor(encoded[i], ans[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr=[0]*(len(encoded)+1)\n",
    "        arr[0]=first\n",
    "        for i in range(0,len(encoded)):\n",
    "            arr[i+1]=(arr[i])^(encoded[i])\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        n = len(encoded)\n",
    "        encoded = [first] + encoded\n",
    "        for i in range(1, n + 1):\n",
    "            encoded[i] ^= encoded[i - 1]\n",
    "        return encoded"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr=[first]\n",
    "        for i in range(len(encoded)):\n",
    "            arr.append(arr[i]^encoded[i])\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        n = len(encoded)\n",
    "        res = [first] * (n + 1)\n",
    "        for i,x in enumerate(encoded):\n",
    "            res[i + 1] = res[i] ^ x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [first]\n",
    "        for e in encoded:\n",
    "            first = first ^ e\n",
    "            arr.append(first)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        decode = [0] * n\n",
    "        decode[0] = first\n",
    "        # 请注意数组下标的调整\n",
    "        for i in range(1, n):\n",
    "            decode[i] = encoded[i-1] ^ decode[i-1]\n",
    "\n",
    "        return decode\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [first,]\n",
    "        for i in encoded:\n",
    "            first = first ^ i\n",
    "            arr.append(first)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        ret=[first]\n",
    "        for item in encoded:\n",
    "            first=item^first\n",
    "            ret.append(first)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        ans = [first]\n",
    "        for en in encoded :\n",
    "            ans.append(en ^ first)\n",
    "            first = ans[-1] \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [0] * (len(encoded) + 1)\n",
    "        arr[0] = first\n",
    "        for i in range(len(encoded)):\n",
    "            arr[i + 1] = arr[i] ^ encoded[i]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr=[first]\n",
    "        for i in range(len(encoded)):\n",
    "            num=encoded[i]^arr[i]\n",
    "            arr.append(num)\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        result = []\n",
    "        result.append(first)\n",
    "        for index, i in enumerate(encoded):\n",
    "            result.append(i ^ result[index])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # encoded[i] = arr[i] XOR arr[i+1]\n",
    "    # encoded[i] XOR arr[i] = arr[i] XOR arr[i+1] XOR arr[i]\n",
    "    # encoded[i] XOR arr[i] = arr[i+1]\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        # arr[i+1] = encoded[i] XOR arr[i]\n",
    "        m = len(encoded)\n",
    "        n = m + 1\n",
    "        arr = [first]\n",
    "        for i, en_num in enumerate(encoded):\n",
    "            arr.append(en_num ^ arr[-1])\n",
    "        return arr\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        n = len(encoded)+1\n",
    "        arr = [first] * n\n",
    "        for i in range(n-1):\n",
    "            arr[i+1] = encoded[i] ^ arr[i]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        result = [first]\n",
    "        for num in encoded:\n",
    "            result.append(result[-1] ^ num)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        res=[]\n",
    "        res.append(first)\n",
    "        for i in encoded:\n",
    "            t=res[-1]^i\n",
    "            res.append(t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [first]\n",
    "        for num in encoded:\n",
    "            arr.append(arr[-1] ^ num)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        last, ans = first, [first]\n",
    "        for num in encoded:\n",
    "            temp, b, time = last, 0, 1\n",
    "            while num or temp:\n",
    "                a, c = temp % 2, num % 2\n",
    "                b += time * int((not a and c) or (a and not c))\n",
    "                time = time << 1\n",
    "                num = num >> 1\n",
    "                temp = temp >> 1\n",
    "            \n",
    "            ans.append(b)\n",
    "            last = b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [first]\n",
    "        for num in encoded:\n",
    "            arr.append(arr[-1]^num)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        l = len(encoded)\n",
    "        ans = []\n",
    "        ans.append(first)\n",
    "        for i in range(l):\n",
    "            pre = ans[-1]\n",
    "            ans.append(pre^encoded[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [first]\n",
    "        for num in encoded:\n",
    "            arr.append(arr[-1] ^ num)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        \n",
    "        encoded=[0]+encoded\n",
    "        res=[]\n",
    "        for i in encoded:\n",
    "            first^=i\n",
    "            res.append(first)\n",
    "\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr=[first]\n",
    "        for i in encoded:\n",
    "            arr.append(i^arr[-1])\n",
    "        return arr\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        ans = [first]\n",
    "        n = len(encoded)\n",
    "        for i in range(n):\n",
    "            ans.append(ans[i] ^ encoded[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr=[]\n",
    "        arr.append(first)\n",
    "        for i in encoded:\n",
    "            t=i^arr[-1]\n",
    "            arr.append(t)\n",
    "        return arr\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [first]\n",
    "        for num in encoded:\n",
    "            arr.append(arr[-1]^num)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        ans = [first]\n",
    "        for num in encoded: ans.append(ans[-1] ^ num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        ans = [first]\n",
    "        for x in encoded:\n",
    "            ans.append(ans[-1] ^ x)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [first]\n",
    "        \n",
    "        for i in encoded:\n",
    "            arr.append(i^arr[-1])\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr=[first]\n",
    "        for num in encoded:\n",
    "            arr.append(arr[-1]^num)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = [first]\n",
    "        for num in encoded:\n",
    "            arr.append(arr[-1] ^ num)\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        ans = [first, ]\n",
    "        for i in encoded:\n",
    "            ans.append(i ^ ans[-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # encoded[i] = arr[i] XOR arr[i+1]\n",
    "    # encoded[i] XOR arr[i] = arr[i] XOR arr[i+1] XOR arr[i]\n",
    "    # encoded[i] XOR arr[i] = arr[i+1]\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        # arr[i+1] = encoded[i] XOR arr[i]\n",
    "        m = len(encoded)\n",
    "        n = m + 1\n",
    "        arr = [first]\n",
    "        for i, en_num in enumerate(encoded):\n",
    "            arr.append(en_num ^ arr[-1])\n",
    "        return arr\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        ans = [first]\n",
    "        for n in encoded:\n",
    "            ans.append(ans[-1] ^ n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr=[first]\n",
    "        for num in encoded:\n",
    "            arr.append(arr[-1]^num)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        arr = []\n",
    "        arr.append(first)\n",
    "        for i in range(len(encoded)):\n",
    "            t = arr[i] ^ encoded[i]\n",
    "            arr.append(t)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int], first: int) -> List[int]:\n",
    "        res = [first]\n",
    "        for secret in encoded:\n",
    "            res.append(secret ^ res[-1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        def calone(n):\n",
    "            ans = []\n",
    "            t = 1\n",
    "            while t <= n:\n",
    "                res = n - t + 1\n",
    "                temp = (res // (t << 1)) * t + min(t, res % (t << 1))\n",
    "                t <<= 1\n",
    "                ans.append(temp)\n",
    "            return ans\n",
    "\n",
    "        n = len(encoded) + 1\n",
    "        total = calone(n) +[0]\n",
    "        bite = 1\n",
    "        while bite <= n:\n",
    "            bite <<= 1\n",
    "        ans = [0] * n\n",
    "        index = 0\n",
    "        while bite > 0:\n",
    "            temp1 = [0]\n",
    "            temp2 = [1]\n",
    "            for i in range(len(encoded)):\n",
    "                if encoded[i] & 1:\n",
    "                    temp1.append(abs(temp1[-1] - 1))\n",
    "                    temp2.append(abs(temp2[-1] - 1))\n",
    "                else:\n",
    "                    temp1.append(temp1[-1])\n",
    "                    temp2.append(temp2[-1])\n",
    "                encoded[i] >>= 1\n",
    "            if (sum(temp1) + total[index]) % 2 == 0:\n",
    "                for j in range(n):\n",
    "                    ans[j] += (2 ** index) * temp1[j]\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    ans[j] += (2 ** index) * temp2[j]\n",
    "            index += 1\n",
    "            bite >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        total = 0\n",
    "        for num in range(1,n+1):\n",
    "            total = total ^ num \n",
    "        sub = 0\n",
    "        for i in range(1,n-1,2):\n",
    "            sub = sub ^ encoded[i]\n",
    "        perm = [total^sub]\n",
    "        for i in range(n-1):\n",
    "            perm.append(perm[i]^encoded[i])\n",
    "        return perm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        perm = reduce(lambda x, y: x ^ y, [_ for _ in range(1, n + 1)])\n",
    "        a = 0\n",
    "        for _ in range(1, n, 2):\n",
    "            a ^= encoded[_]\n",
    "        a ^= perm\n",
    "        ret = [a]\n",
    "        for _ in range(n - 1):\n",
    "            ret.append(a ^ encoded[_])\n",
    "            a ^= encoded[_]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded)\n",
    "        k = 0\n",
    "        for i in range(1, n+2):\n",
    "            k ^= i\n",
    "        num = 0\n",
    "        for i in range(1, n+1, 2):\n",
    "            num ^= encoded[i]\n",
    "        res = list()\n",
    "        res.append(num ^ k)\n",
    "        for i in range(0, n):\n",
    "            res.append(res[i] ^ encoded[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        all_xor = 0  # XOR of all numbers from 1 to n\n",
    "        for i in range(1, n + 1):\n",
    "            all_xor ^= i\n",
    "        \n",
    "        xor_except_first = 0  # XOR of all numbers from perm[1] to perm[n]\n",
    "        for i in range(1, n-1, 2):  # Iterate over even indices of encoded\n",
    "            xor_except_first ^= encoded[i]\n",
    "        \n",
    "        # Get the first number of perm\n",
    "        perm = [all_xor ^ xor_except_first]\n",
    "        \n",
    "        # Decode the rest of perm using encoded\n",
    "        for num in encoded:\n",
    "            perm.append(perm[-1] ^ num)\n",
    "        \n",
    "        return perm\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        cnt = 0\n",
    "        for num in range(1, len(encoded)+2):\n",
    "            cnt ^= num\n",
    "        for i in range(1, len(encoded), 2):\n",
    "            cnt ^= encoded[i]\n",
    "        res.append(cnt)\n",
    "        for i in range(len(encoded)):\n",
    "            cnt ^= encoded[i]\n",
    "            res.append(cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n=len(encoded)+1\n",
    "        cur=0\n",
    "        for x in range(1,n+1):\n",
    "            cur^=x\n",
    "        res=cur\n",
    "        cur=0\n",
    "        for i in range(1,n-1,2):\n",
    "            cur^=encoded[i]\n",
    "        #求出perm[0]\n",
    "        p=res^cur\n",
    "        ans=[p]\n",
    "        cur=0\n",
    "        for x in encoded:\n",
    "            cur^=x\n",
    "            ans.append(cur^p)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        total = 0\n",
    "        for num in range(1,n+1):\n",
    "            total = total ^ num \n",
    "        sub = 0\n",
    "        for i in range(1,n-1,2):\n",
    "            sub = sub ^ encoded[i]\n",
    "        perm = [total^sub]\n",
    "        for i in range(n-1):\n",
    "            perm.append(perm[i]^encoded[i])\n",
    "        return perm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        ret = []\n",
    "        num = len(encoded)\n",
    "        arr_0 = 0\n",
    "        for i in range(0, len(encoded)):\n",
    "            arr_0 ^= (i + 1)\n",
    "            if (num & 1):\n",
    "                arr_0 ^= encoded[i]\n",
    "            num = num - 1\n",
    "        ret.append(arr_0 ^ (len(encoded) + 1))\n",
    "        for i in range(0, len(encoded)):\n",
    "            ret.append(ret[-1] ^ encoded[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n=len(encoded)+1\n",
    "        cur=0\n",
    "        for x in range(1,n+1):\n",
    "            cur^=x\n",
    "        res=cur\n",
    "        cur=0\n",
    "        for i in range(1,n-1,2):\n",
    "            cur^=encoded[i]\n",
    "        #求出perm[0]\n",
    "        p=res^cur\n",
    "        ans=[p]\n",
    "        cur=0\n",
    "        for x in encoded:\n",
    "            cur^=x\n",
    "            ans.append(cur^p)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        m = reduce(xor, encoded[1::2]) ^ reduce(xor, range(1, len(encoded)+2))\n",
    "        return [m, *((m := m ^ x) for x in encoded)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n, a, b = len(encoded)+1, 0, 0\n",
    "        ans = [0] * n\n",
    "\n",
    "        for i in range(0, n-1, 2):\n",
    "            a = a ^ encoded[i]\n",
    "        for i in range(1, n+1):\n",
    "            b = b ^ i\n",
    "        \n",
    "        ans[n-1] = a ^ b\n",
    "        for i in range(n-2, -1, -1):\n",
    "            ans[i] = ans[i+1] ^ encoded[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(encoded)\n",
    "        s = reduce(xor, range(1, n + 2))\n",
    "        # print(s, 1 ^ 2 ^ 3)\n",
    "        tmp = 0\n",
    "        for i in range(1, n, 2):\n",
    "            tmp ^= encoded[i]\n",
    "        num1 = s ^ tmp\n",
    "        ans = [num1]\n",
    "        for e in encoded:\n",
    "            ans.append(e ^ ans[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n, a, b = len(encoded), 0, 0\n",
    "        ans = [0] * (n + 1)\n",
    "        for i in range(0, n, 2):\n",
    "            a ^= encoded[i]\n",
    "        for i in range(1, n + 2):\n",
    "            b ^= i\n",
    "        ans[n] =  a ^ b\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans[i] = ans[i + 1] ^ encoded[i]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        total = 0\n",
    "        # 隔位异或可以得到 1 2 ... n - 1\n",
    "        for i in range(0, n - 1, 2):\n",
    "            total ^= encoded[i]\n",
    "        ans = [0] * n\n",
    "        totaln = 0\n",
    "        for i in range(1, n + 1):\n",
    "            totaln ^= i\n",
    "        ans[n - 1] = totaln ^ total\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = ans[i + 1] ^ encoded[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        check = 0\n",
    "        n = (len(encoded) + 1)\n",
    "        nums = [0] * n\n",
    "        for i in range(1,n + 1):\n",
    "            check ^= i\n",
    "        res = 0\n",
    "        for per in range(1,len(encoded),2):\n",
    "            res ^= encoded[per]\n",
    "        nums[0] = res ^ check\n",
    "\n",
    "        for i in range(1,n):\n",
    "            nums[i] = encoded[i-1]^nums[i-1]\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        # def calone(n):\n",
    "        #     ans = []\n",
    "        #     t = 1\n",
    "        #     while t <= n:\n",
    "        #         res = n - t + 1\n",
    "        #         temp = (res // (t << 1)) * t + min(t, res % (t << 1))\n",
    "        #         t <<= 1\n",
    "        #         ans.append(temp)\n",
    "        #     return ans\n",
    "\n",
    "        # n = len(encoded) + 1\n",
    "        # total = calone(n) +[0]\n",
    "        # bite = 1\n",
    "        # ans = [0] * n\n",
    "        # index = 0\n",
    "        # while bite <= n:\n",
    "        #     temp1 = [0]\n",
    "        #     temp2 = [1]\n",
    "        #     for i in range(len(encoded)):\n",
    "        #         if encoded[i] & 1:\n",
    "        #             temp1.append(abs(temp1[-1] - 1))\n",
    "        #             temp2.append(abs(temp2[-1] - 1))\n",
    "        #         else:\n",
    "        #             temp1.append(temp1[-1])\n",
    "        #             temp2.append(temp2[-1])\n",
    "        #         encoded[i] >>= 1\n",
    "        #     if (sum(temp1) + total[index]) % 2 == 0:\n",
    "        #         for j in range(n):\n",
    "        #             ans[j] += (2 ** index) * temp1[j]\n",
    "        #     else:\n",
    "        #         for j in range(n):\n",
    "        #             ans[j] += (2 ** index) * temp2[j]\n",
    "        #     index += 1\n",
    "        #     bite <<= 1\n",
    "        # return ans\n",
    "\n",
    "        num = 0\n",
    "        nums = [0] * (len(encoded) + 1)\n",
    "        \n",
    "        for i in range(1, len(nums) + 1):\n",
    "            num ^= i\n",
    "        \n",
    "        count = 0\n",
    "        for j in range(1, len(encoded), 2):\n",
    "            count ^= encoded[j]\n",
    "        \n",
    "        nums[0] = num ^ count\n",
    "        \n",
    "        for i in range(1, len(encoded) + 1):\n",
    "            nums[i] = encoded[i - 1] ^ nums[i - 1]\n",
    "        \n",
    "        return nums\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n=len(encoded)+1\n",
    "        total=0\n",
    "        for i in range(1,n+1):\n",
    "            total^=i\n",
    "        p=0\n",
    "        for i in range(1,n-1,2):\n",
    "            p^=encoded[i]\n",
    "        res=[0]*n\n",
    "        res[0]=total^p\n",
    "        for i in range(1,n):\n",
    "            res[i]=encoded[i-1]^res[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n, a, b = len(encoded) + 1, 0, 0\n",
    "        ans = [0] * n\n",
    "        for i in range(0,n - 1,2):\n",
    "            a ^= encoded[i]\n",
    "        for i in range(1,n + 1):\n",
    "            b ^= i\n",
    "        ans[n - 1] =  a ^ b\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            ans[i] = ans[i + 1] ^ encoded[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        x=encoded[0]\n",
    "        a=1\n",
    "        n=len(encoded)+1\n",
    "        for i in range(2,n+1):\n",
    "            a^=i\n",
    "        for i in range(2,n-2,2):\n",
    "            x^=encoded[i]\n",
    "        ans=deque()\n",
    "        p=x^a\n",
    "        ans.append(p)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            p^=encoded[i]\n",
    "            ans.appendleft(p)\n",
    "        return list(ans)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        total = reduce(xor, range(1, n + 1))\n",
    "        odd = 0\n",
    "        for i in range(1, n - 1, 2):\n",
    "            odd ^= encoded[i]\n",
    "        \n",
    "        perm = [total ^ odd]\n",
    "        for i in range(n - 1):\n",
    "            perm.append(perm[-1] ^ encoded[i])\n",
    "        \n",
    "        return perm\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        tot = 0\n",
    "        for i in range(n+1):\n",
    "            tot ^= i\n",
    "        p = [0] * n\n",
    "        for i in range(1,n-1,2):\n",
    "            p[0] ^= encoded[i]\n",
    "        p[0] ^= tot\n",
    "        for i in range(1,n):\n",
    "            p[i] = p[i-1] ^ encoded[i-1]\n",
    "        return p\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decode(self, encoded: List[int]) -> List[int]:\n",
    "        n = len(encoded) + 1\n",
    "        total = reduce(xor, range(1, n + 1))\n",
    "        odd = 0\n",
    "        for i in range(1, n - 1, 2):\n",
    "            odd ^= encoded[i]\n",
    "        \n",
    "        perm = [total ^ odd]\n",
    "        for i in range(n - 1):\n",
    "            perm.append(perm[-1] ^ encoded[i])\n",
    "        \n",
    "        return perm"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
